//
//  Problem1552.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/24.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1552. 两球之间的磁力
 在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。
 已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
 给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。

 示例 1：
     1,2,3,4,7
     *     * *
     输入：position = [1,2,3,4,7], m = 3
     输出：3
     解释：将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。
 示例 2：
     输入：position = [5,4,3,2,1,1000000000], m = 2
     输出：999999999
     解释：我们使用位于 1 和 1000000000 的篮子时最小磁力最大。
 提示：
     n == position.length
     2 <= n <= 10^5
     1 <= position[i] <= 10^9
     所有 position 中的整数 互不相同 。
     2 <= m <= position.length
 */
@objcMembers class Problem1552: NSObject {
    func solution() {
//        print(maxDistance([1,2,3,4,7], 3))
        print(maxDistance([5,4,3,2,1,1000000000], 2))
    }
    
    /*
     二分法
     套路：假设我们知道答案，然后根据答案倒退球的个数m1，看看比较m1和m，找到最符合的答案。
     首先确定left和right，
     1: left = 1，因为最小的距离就是1
     2: right = max - min，就是数组中的最大间距，这需要我们排序数组
     我们计算出mid，看看mid的间距支持摆几个球m1，计算m1和m的比较
     1: 如果m1 = m：间距mid肯定符合条件，但是有能有比mid更大一点的值，也满足m1=m，left = mid + 1
     2: 如果m1 > m：间距mid肯定符合条件，我都支持比m多的球，但是mid肯定不是最大值，需要left = mid + 1
     3: m1 < m,不符合
     */
    func maxDistance(_ position: [Int], _ m: Int) -> Int {
        var maxValue = 0
        let sortList = position.sorted()
        var l = 1, r = sortList.last! - sortList.first!
        var mid = 0
        
        var num = 0
        while l <= r {
            mid = l + (r - l) >> 1
            // 看看间距是mid时，最多有几个位置能放球
            num = checkNum(sortList, mid)
            
            if num >= m {   // 说明 mid 满足条件，我们需要更大一点的mid
                l = mid + 1
                maxValue = mid
            } else {
                r = mid - 1
            }
        }
        return maxValue
    }
    
    // 根据间距：看看能在几个位置放球
    func checkNum(_ position:[Int], _ mid: Int) -> Int {
        var n = 1
        var left = position[0]
        for i in 1..<position.count {
            if position[i] - left >= mid {
                n += 1
                left = position[i]
            }
        }
        return n
    }
}
